Image Retrieval

For Buildings and Scenic Spots

指導教授：賴尚宏

組員：葉家如

      曹瀠方

      謝涵宇

一、摘要

影像比對、影像辨識是劃時代的演算技術。現今隨著網路的進展與數位相機、攝影機的普及，資料型態不再僅限於文字，影像搜尋引擎的想法國內不少學系在探討、研究；手術Ｘ光片的判讀；晶片瑕疵的辨識；警方的指紋辨識系統；犯罪現場錄影帶裡嫌犯的人臉辨識。以上種種，皆是運用影像比對與辨識技巧的實例。這次專題我們實際演算影像比對的方法與流程，一步步了解影像比對如何建立比對用資料庫、取特徵值的不同方法、求兩張圖片差異的算術技巧….等。

取圖片特徵值的方式，我們有三種演算法，這些演算法是根據前人經驗統整出的一些有較好影像比對結果的方法，分別是圖片質地特徵值、顏色特徵值、SIFT特徵值。算兩張照片的distance(差異)有兩種算法 : Euclidean distance與Cosine distance。另有，SVM與Adaboost等machine learning的評估方法。並以mAP與accuracy兩種方法來評估資料庫的完整性。從結果分析，發現影像比對會因影像色調與取景角度與型態而有所侷限。若能在進行影像比對時，有正規化的動作，像是限制取景時的型態，或是色調的統一….等，這些問題若能在進行影像比對時克服，比對時的錯誤就可以減少，影像比對的應用就可以更可靠、更準確。

我們以學校的建築物當資料庫，大約有三百多張照片，每張照片皆是1280*960大小。當使用者以手機照下學校中的建物場景時，圖檔以網路傳輸的方式傳至server端，以不同的方式運算此圖檔的各種特徵值，再與資料庫的特徵值進行比對。比對的結果回傳至client端 (即手機)，告知使用者此建物為何，身處何方。處理影像比對的同時，並結合android手機平台，使專題富趣味性與挑戰性。

二、簡介              

2.1研究動機

隨著科技的快速發展，現代社會中幾乎每個家庭都擁有一台數位相機，且人手一台具備照相功能的手機，因此每到一個地方遊玩總會按下快門、抓住每個值得紀念的瞬間，但隨著照片量的增加，一旦疏於整理或者因為時光的流逝，往往會發生照片中的景點明明是如此的眼熟，卻老是記不起詳細的拍攝地點的狀況，這時，該如何是好呢？既然人腦沒辦法記住世界上的所有景點，有沒有可能讓電腦來做這件事呢？

於是我們產生了以下的想法：只要使用者上傳一張照片，電腦就能立即判斷拍攝的地點並回傳給使用者，如此一來不僅能夠找到舊照片的拍攝地點，人在戶外迷路時，就算沒有GPS，也能夠利用手機的拍照功能和上網功能，拍攝附近的顯著地標後上傳，就能輕輕鬆鬆了解自己的所在地點，而這樣的一個平台，除了兼具方便性和實用性之外，又能發揮我們學到的影像處理、嵌入式設計、網路傳輸的相關技巧。

2.2系統功能 

首先，影像比對有許多取feature的方法，我們希望能夠整合出一支比對的程式，使得影像比對時能夠同時考慮畫面的顏色分布、建築物的結構，就算影像經過放大縮小、角度不同、光影不同也能夠產生正確的判斷結果。

又，這樣的影像比對需要大量的資料庫和快速的運算，直接寫成手機的應用軟體的可行性不高，所以我們必須將程式分成使用者端程式和伺服器端程式，使用者端的程式(也就是在手機上運作的程式)負責將input圖片上傳到伺服器，而伺服器端的程式又分成兩個部分，用來建立資料庫的database程式以及用來比對特徵點的query程式，伺服器進行比對後再回傳給使用者端，所以中間的傳輸過程須要使用網路傳輸的功能。

2.3組員分工

三、系統架構     

   3.1實驗平台

Client端：

搭載android系統的手機平台 : HTC Hero

HTC Hero 規格 :

 處理器 :  Qualcomm MSM 7200A 528 MHz ARM processor

網路 : Quad-band GSM/GPRS/EDGE (850/900/1800/1900 MHz)

相機 : 5.0 megapixel color camera with auto focus

Server端：

      WindowsXP

   3.2軟體架構說明

程式語言 : C

實作平台 : Visual studio C++ 2005 (professional版本)

支援程式庫 : OpenCV、CxImage

             幫助讀取圖片，取RGB值。

(1) Client端----上傳使用者拍攝照片、比對結果的顯示。

Client 與 Server網路程式 : 回傳使用者拍攝的照片至server端，並將比對結果傳回顯示。

(2) Server端----擷取使用者上傳照片的特徵值、與資料庫進行比對、回傳比對結果。

擷取圖片特徵值 : 以不同演算法擷取圖片特徵值，取出的texture、color、BoF三種特徵值與database中的特徵值運算euclidean distance或是cosine distance，以評估比對好壞。20維的properties特徵值則當作machine learning的input。統整各種方法比對出的結果，回傳結果至client端。在server端的比對部分我們寫了兩支程式 :

1.      取database的特徵值

2.      取query (input image) 的特徵值與database的特徵值做比對，回傳與query最相似的地點。

 4.1取feature

        4.1.1 Texture   

取特徵值的方法之一，主要是看pixel值的相關排列、組合。取出的特徵值是一個矩陣，稱之為co-occurrence matrix，取值過程示範如下 :

若有一張圖(size : 5X5)，讀出它的pixel值如 :

Co-occurrence可以是看上下、左右、斜對角pixel值的發生關係，並做計數的動作。因為範例pixel值介於0~3，所以co-occurrence matrix就會是一個4X4大小的matrix。

左右關係的co-occurrence matrix 特徵值 :

因為pixel值左右為0的發生次數為1，所以co-occurrence matrix的(0,0)坐標值為1。再看回size 5X5的那張圖，Pixel值左為2,右為3的發生次數有2個，所以坐標(2,3)的紀錄值為2，以此類推得到一個依圖片pixel值左右關係為根據的co-occurrence matrix ( row代表左邊pixel值，column代表右邊pixel值 )。另外，也可以看上下關係與斜對角關係，co-occurrence matrix如下 :

上下關係的co-occurrence matrix 特徵值 :

(row代表上面的pixel值，column代表下面的pixel值)

斜對角關係的co-occurrence matrix 特徵值 :

(row代表左上pixel值，column代表右下pixel值)

以上述方式，我們取出圖片的左右、上下、(左上右下)斜對角關係的三種co-occurrence matrix特徵值，實際圖片的pixel值介於0~255，加上資料庫裡的照片是彩圖，RGB要一起看，所以co-occurrence matrix的大小便是(256^3)*(256^3)，然而這樣大小的co-occurrence matrix，裡頭有大部分的值會是0，在比對時會失去鑑別度，因此在取texture特徵值前，我們先將圖片quantize，這部分我們試了bin3、bin10、bin20。Bin3 pixel值介於 0~2; bin10介於0~9; bin 20介於0~19。之後再以同樣手法取co-occurrence matrix特徵值。

4.1.2 Color coherence vector     

這個取feature的方法，是利用一張圖片的色塊大小作區分。我們可以知道圖片的相似度可以用顏色作區分，因為這兩張圖片如果是一樣的，他們顏色比例應該要相同。但只看顏色的比例，又太武斷。所以給了一個臨界值，當色塊比例大於臨界值時分在alpha，小於臨界值時分在beta。因此就能清楚判別下面的圖片。

在實作時，要先對顏色切BIN(把顏色0~255分成幾塊)。因為顏色分別是由RGB，3個byte所組成，這樣會有1677216個(256^3=1677216)顏色與圖片大小(1280*960=1228800)太接近，所以在找色塊時，色塊都會被切得太小而導致成效不好。所以分別把顏色切成4種BIN(BIN=3,BIN=10,BIN=20,BIN=26)。接下來就是要對圖片找connected component。對找出來的component找到相對應的顏色，並計算component的大小。如果大於臨界值就放到alpha，否則放到beta。再找下一個component，直到原圖的每一個pixel都已經分好程式才會結束。

以下是程式的流程圖 :

        4.1.3 SIFT      

SIFT(Scale-invariant feature transform)也就是尺度不變特徵轉換，為一個尺度不變的特徵點擷取與描述演算法。對於旋轉、位移、雜訊與亮度差異可不受其干擾，將影像間的特徵點找出並匹配。

            SIFT主要可分為四個步驟：

(1) 尺度空間極值偵測：在每個octave中，將影像作四次高斯模糊後，兩兩相減，也就是作difference-of-Gaussian (DOG) ，如圖所示。                          

每個 octave中，找出26個鄰居像素(如圖所示)中的區域極大值(localmaximum)或區域極小值(local minimum)，則稱此點為極值點。

(2) 特徵點位置最佳化：這一步驟的目的在刪去一些不穩定的候選特徵點，為了達成此目的，使用以下式子(如圖):  

其中，x為候選特徵點，D 為 DOG後的結果，而T為轉置矩陣。

               又，由x和D，可以求出一個偏移量(offset): ，由下式說明

      最後，刪除掉區域極小值，也就是邊緣的候選特徵點。

(3) 計算特徵點方向性：這個步驟最主要的目的就是為了形成特徵點描述的前置作業。選定尺度後，計算local gradient directions，再產生其histogram，最後再將histogram定向。

(4) 特徵點描述：求出每個特徵點的方向後，接下來就是特徵點的描述。首先，以特徵點的方向為基準，將以特徵點為中心的區塊旋轉到以特徵點方向為上，如此一來，特徵點就可以達到旋轉不變性。然後在此區塊內將 16 *16 的範圍切割為 4 *4 的子區塊，分別統計每個子區塊內的方向直方圖，也就是說在4*4 的子區塊中，每個子區塊統計八個方向，總共特徵點的向量維度為8*4*4=128。

實作的步驟如下，首先我們在網路上找到由David Lowe提供的siftWin32.exe執行檔，該執行檔能找出*.pgm的圖片的SIFT feature，然後我們使用OpenCV library 將原本的*.jpg檔案轉換成*.pgm並輸入至siftWin32.exe後，該程式即產生紀錄SIFT feature的*.key檔，而此檔內記錄著所有該圖的128維的SIFT feature。

此種比對方法的準確率極高，但有一個極大的缺點，比對所耗費的時間太長，不符合我們的期望，故只將此方法列為一個比較的基準，如果有方法可以接近此方法的準確率代表該方法相當準確。

為了減少比對時間，我們使用了k-means分群法，k-means是一種分割式分群法(partitional clustering)，我們必須先指定群聚的數目，然後藉著反覆疊代運算，逐次降低一個誤差目標函數的值，直到目標函數不再變化，就達到分群的最後結果。其主要目標是要在大量高維的資料點中找出具有代表性的資料點，這些資料點可以稱為是群中心(cluster centers)、代表點(prototypes)、codewords等，我們找到中心點後，再去找與每個feature點最接近的cluster centers，則該點就屬於那個cluster，藉此將feature點分為指定個群聚的數目。

於是，我們使用了hammming embedding，此種方法的簡易流程如下，先用k-means將feature點分群後，將feature點投射到同一平面上，找到database中每個群(cluster)內每個維度的中位數後將同群內的比中位數小和比中位數大的數字分別化成0和1的形式，如此一來可以減少花在比對和自己太遠的feature的時間。

但是這個方法的結果並不理想，首先，所需的時間並不如想像的大量減少，比對一張依然需要用上3到4個小時的時間，另外就是結果的準確度也不理想，所以也不採納此種方法。

最後我們採用了bag-of-feature的方法，這種方法的的概念如下：經過k-means將feature點分群後，同一群內的feature點的相似度會很高，所以兩張相似的圖片，群內的feature點個數分布會很接近，我們統計每張圖的每個群的feature個數後，將之化成histogram的形式，再進行histogram的比對。

此種方法速度快、正確率也相當接近直接計算SIFT difference的方法，所以在SIFT的部分最後就採用了bag-of-feature的方法。

4.3評估方法       

我們蒐集到學校的圖片共304張，將之分為43個景點後編排為class 0到class42，每個class約有2到12張圖片不等，為了評估前述方法的準確性與資料庫的完整性，我們將每個class編號0的圖片抽出來當作query，也就是input data，剩下的圖片當作database，並執行我們的程式來進行評估，其中由4.2提到的比對方法來排rank，兩張圖差異越小rank越小。

評估方法，分為以下兩種 :

(1) mAP

全名為Mean Average Precision 平均準確率。數學式子如下：

n : number of relevant document, ex: class 0總共有5張圖,N=5。

        P( r ) : the sequence rank of the relevant, ex : class 0 的 rank 為 (1,5,8,9,12)

                   N : the number of AP

(2)Accuracy

Machine learning : 對某個query而言，檢查是否有對到相對應的label。Ex: query為class 10 應該要對到label為 10的label。

Feature extraction 所取出的feature經過Euclidean與cosine 的計算，分別算出query對各個class的AP，找出最大的AP判斷class是否與query所屬的class相同。相同的話，就當作是有對到相對應的class，不同的話，就是沒有對到。

計算43個query(label由0~42)是否有對到，當作accuracy的值。EX:有20個有對到accuracy就是20/43(=0.465)。

(3)兩者比較 :

mAP的計算方法，比較像是在對database算整體的正確率。mAP在作分析數據時，相對於accuracy可以有較快的速度(因為只要計算與自己相同class的rank)。但是在training時並沒有辦法得知，一張圖片是否有對應到應對應的class。

   4.4網路           

這部分有分Client和 Server，我們在client端發送圖片給server端作運算。再由server端，把結果回傳。

步驟如下 :

Step1 : client 與server建立socket連線。

Step2 : 連線建立，互傳資料。

五、結果與數據分析  

使用先前的database的數據結果並以Euclidean distance為rank時的依據如下：

以cosine distance為rank依據的話，數據則是 :

後來我們將照片縮小為320*240，並稍微修正了比對方法，而且更新了database中的圖片。

以下是我們database中的部分圖片，每個顯著的景點分為一個class：

更新資料庫後，經過分析比較，我們決定同時取出以下5種feature：

Texture以左右相關(bin3)、上下相關(bin3)、斜對角相關(bin3)

color coherence vector以tou1000 (bin10)

BoF以cluster=200

並以Euclidean distance當作rank時的依據，比對的最終數據如下：

Accuracy  = 49 / 51 = 0.960784 = 96.08%

可以看出正確率大幅度的提升，可見優異的資料庫也是此系統不可或缺的要素。

五、網路部分

網路部分使用socket做連線，目前已經發展出server端為windows系統，cilent端為linux系統的網路連線程式，已可正常運作，連線所需時間約0.1秒。

六、未來與展望

我們希望未來此軟體能夠擴充為一個較大範圍的影像比對軟體，像是囊括全台灣著名景點的影像比對軟體，如此一來才能實現我們一開始為大眾著想的初衷，也期望能夠發展成另一種形式的較小範圍導覽軟體，像是花卉博覽會的導覽軟體，只要拍攝所在地點周圍的景物，就能夠回傳使用者所在的展場和附近的花卉資訊。

而這樣的平台未來也可以發展其他影像類型的軟體，像是花卉類型的影像比對、汽車型號的影像比對，更甚至是條碼的影像比對等等，雖然不同類型的影像比對著重的特徵點取法不太一樣，花卉類的可能需要分析花朵結構等等，但也因此充滿各種不同的可能性。

八、參考資料

[1]Cximage http://www.xdp.it/cximage.htm

[2]Client & server http://www.codeproject.com/KB/IP/server_client_sockets.aspx

[3]Greg Pass and Ramin Zabih and Justin Miller,"Comparing Images Using Color Coherence Vectors", Computer Science Department Cornell University Ithaca, NY 14853

[4]SIFT demo program by David G. Lowe http://www.cs.ubc.ca/~lowe/keypoints/

[5]OpenCV Library http://www.opencv.org.cn/index.php/%E9%A6%96%E9%A1%B5

[6] 吳俊霖、陳彥良 "A Robust Feature-Based Image Registration Method for Differently Exposed Image Sequences "

[7] Arati S. Kurani, Dong-Hui Xu, Jacob Furst, Daniela Stan Raicu, "CO-OCCURRENCE MATRICES FOR VOLUMETRIC DATA", Intelligent Multimedia Processing Laboratory.

[8] HTC hero官網 : http://www.htc.com/www/product/hero/specification.html